\documentclass[12pt]{article}
\usepackage{amsfonts}
%\documentstyle[12pt,amsfonts]{article}
%\documentstyle{article}
\usepackage{graphicx}
\setlength{\topmargin}{-.5in}
\setlength{\oddsidemargin}{0 in}
\setlength{\evensidemargin}{0 in}
\setlength{\textwidth}{6.5truein}
\setlength{\textheight}{8.5truein}
%\input ../basicmath/basicmathmac.tex
%
%\input ../adgeomcs/lamacb.tex
\input mac.tex
\input mathmac.tex

\def\fseq#1#2{(#1_{#2})_{#2\geq 1}}
\def\fsseq#1#2#3{(#1_{#3(#2)})_{#2\geq 1}}
\def\qleq{\sqsubseteq}

%
\begin{document}
\begin{center}
\fbox{{\Large\bf Spring, 2009 \hspace*{0.4cm} CIS 511}}\\
\vspace{1cm}
{\Large\bf Introduction to the Theory of Computation\\
Homework 2\\}
\vspace{0.5cm}
\textbf{Jian Chang, Sanjian Chen, Yeming Fang}\\
\vspace{0.2cm}
\itshape{\{jianchan,sanjian,yemingf\}@cis.upenn.edu}

\end{center}

\vspace {0.25cm}\noindent
{\bf Solution B1.}

\vspace {0.25cm}\noindent
(a) Proof: Figure \ref{fig_B1} is such a NFA.

\begin{figure}[h]
\begin{center}
  % Requires \usepackage{graphicx}
  \includegraphics[width=0.5\linewidth]{fig_1}
  \caption{The NFA accept the strings set $L_n$}\label{fig_B1}
\end{center}
\end{figure}

\vspace {0.25cm}\noindent
(b) Proof: Construct a DFA $D = (Q,\Sigma,\delta,q_0,F)$ as following:
\begin{itemize}
    \item $Q$ is a set of $2^n$ states, label these states with $n$ binary digits from $(0, \ldots, 0)$ to $(1, \ldots, 1)$
    \item $\Sigma= \{a_1, \ldots, a_n\}$.
    \item $q_0$ is the state labeled $(0, \ldots, 0)$.
    \item The rest states besides $q_0$ belong to $F$.
    \item Define $\delta$ as: $\delta(q_i,a_i)=q_j$, $q_j$ is the state flip the $i-th$ bit of $q_i$'s label.
\end{itemize}

It is easy to show from the construction that: if the $i-th$ bit in the labels of the states is $1$, it indicates there are odd number of $a_i$ in the input string. Then the DFA accept the language $L_n$.

\vspace {0.25cm}\noindent
(c) Proof: Following the steps to test the DFA accepting the language $L_n$.
\begin{enumerate}
    \item Give every state in the DFA with a label of n binary digits, initiate all the labels as $(0, \ldots, 0)$.
    \item Input two string $a_1$ and $a_1 a_1$, the DFA must arrive at two different states $q_1$ and $q'_1$, or else it will contradict with the fact this DFA accepting the language $L_n$. Then change the first bit of the label of the two states into $1$ and $0$, respectively.
    \item Continue similar steps as (2) by continuing input string $a_i$, $a_i a_i$ (i from 2 to n) from states $q_{i-1}$ and $q'_{i-1}$, in each step the DFA must arrive at two different states $q_i$ and $q'_i$, or else it will contradict with the fact this DFA accepting the language $L_n$. Copy the label from the previous stage $q_{i-1}$ or $q'_{i-1}$, and change the $ith$ bit of the label of the two states into $1$ and $0$, respectively.
\end{enumerate}
It is easy to show from the testing steps above: It will finally label at least $2_n$ states in the DFA with $2_n$ different labels from from $(0, \ldots, 0)$ to $(1, \ldots, 1)$. Then we prove that any DFA accepting $L_n$ has at least $2^n$ states.

\vspace{0.25cm}
\noindent
{\bf Solution B2.}

\vspace{0.25cm}
\noindent (a) Proof:

Since language $C$ contains finite strings and each string has
finite length, we can easily construct a DFA/NFA to accept $C$.
Denote the corresponding regular expression of language $C$ as $U$.

Given $c \in \Sigma$, we have string $cu \in \s{L}[cU]$, where string $u \in \s{L}[U]$.
From the definition of $L_M$, we have that $\forall w\in L_M$, $w\in \s{L}[U(cU)^*]$. This means $L_M$ can be
represented by regular expression $U(cU)^*$, then we conclude that $L_M$ is a regular language.

\vspace{0.25cm}
\noindent (b) The recursive rule is given as following (We credit Wikipedia for the algorithm):

Construction of a Menger sponge can be visualized as follows:
\begin{enumerate}
    \item Begin with a cube.
    \item Divide every face of the cube into 9 squares. This will sub-divide the cube into 27 smaller cubes.
    \item Remove the cube at the middle of every face, and remove the cube in the center, leaving 20 cubes. This is a Level 1 Menger sponge.
    \item Repeat steps 1-3 for each of the remaining smaller cubes.
\end{enumerate}

The second repetition will give you a Level 2 sponge, the third a Level 3 sponge, and so on. The Menger sponge itself is the limit of this process after an infinite number of iterations. Figure \ref{fig_B2} illustrates the process.

\begin{figure}[h]
\begin{center}
  \includegraphics[width=0.9\linewidth]{fig_2}
  \caption{The construction of Menger Sponge}\label{fig_B2}
\end{center}
\end{figure}

\vspace {0.25cm}\noindent
{\bf Solution B3.}

\vspace {0.25cm}\noindent
(i) Proof:

$\forall$ string $r \in \s{L}[R]$, since $R \cong S^{*}T$,
so $r=s^nt, n\geq0, s \in \s{L}[S], t \in \s{L}[T]$.

\begin{itemize}
\item When $n=0$, $r=t$, so $r \in \s{L}[SR+T]$.
\item When $n>0$, we have $r'=s^{n-1}t \in \s{L}[R], n-1 \geq 0 $. So $r=ss^{n-1}t=sr' \in \s{L}[SR+T]$.
\end{itemize}

So we see that, for each string $r\in \s{L}[R]$, it is in $\s{L}[SR+T]$.\\

In the other direction, $\forall$ string $x \in \s{L}[SR+T]$,
$x$ is either $t \in \s{L}[T]$, or is $sr'$, where $s \in \s{L}[S], r' \in \s{L}[R]$.

\begin{itemize}
\item When $x=t \in \s{L}[T]$, $x \in \s{L}[S^*T]$, so $x \in \s{L}[R]$.
\item When $x=sr'$, since $r'=s^kt, k \geq 0$, so $x=s^{k+1}t \in \s{L}[S^*T]=\s{L}[R]$.
\end{itemize}
So we see that, for each string $x \in \s{L}[SR+T]$, it is in $\s{L}[R]$. Therefore, we have $R \cong  SR + T$.

\vspace {0.25cm}\noindent
(ii) Proof:

Observing that $R \cong  SR + T$ implies that for every $k\geq 0$,
$$R \cong  S^{k+1}R + (S^{k} + S^{k-1} + \ldots + S^{2} + S + \epsilon)T $$

When $k \rightarrow \infty$,
$$R \cong  S^{k+1}R + S^*T $$

\begin{itemize}
    \item It is trivial to show that for all string $w \in \s{L}[S^*T]$, $w \in \s{L}[S^{k+1}R + S^*T]$.
    \item For any string $w \in \s{L}[SR + T]$, and the length of $w$ is n. Notice that, for all the string $w' \in \s{L}[S^{k+1}R]$, $k>n$, the  length of $w$ is greater than n. Then $w$ must belong to $\s{L}[S^*T]$.
\end{itemize}

Then we conclude that if $R \cong  SR + T$, then $R \cong  S^{*}T$.

\vspace {0.25cm}\noindent
(iii) Proof:
\begin{itemize}
    \item For $X_{1}$, let $T=S_{1,2}X_2+\cdot\cdot\cdot+S_{1,n}X_n+T_1$ and $S_1=S_{1,1}$
($S_{1,1}$ and $S_1$ does not contain $\epsilon$), $S_1$ and $T$ are regular expressions. From the problem (ii) proved above, we know that $X_1\cong S_1^*T$.
    \item Replace $X_1$ with $S_1^*T$ in the 2nd equation. In the same way we get $X_2\cong S_2^*T'$.
    \item Go on this process, we will have $X_n \cong S_n^*T, 1 \leq k \leq n$, which makes the unique solution to this system of equations.
\end{itemize}

\vspace {0.5cm}\noindent
{\bf Solution B4.}
Proof:
Since Language $R$ is regular, it is easy to construct a NFA with single start state and single final state. $N = (Q,\Sigma,\delta,q_0,F=\{q_F\})$ with $R$ as its language.\\

We define $\delta_B$ as the function travel backwards in a NFA, $\delta_B(q,a)=p$ is equal to $\delta(p,a)=q$, and similarly we can define $\delta_B^*$.\\

Then we construct a NFA $N' = (Q', \Sigma',\delta',q'_0,F')$ as following:
\begin{itemize}
    \item $Q' = \{ (q_i,q_j) \in Q \times Q \ | \ \exists u,v$, $uv \in R, |u|=|v|, \delta^*(q_0,u)= \delta_B^*(q_F,v)$, x is the prefix of u, y is the suffix of v, $|x|=|y|$, and $\delta^*(q_0,x)=q_i, \delta_B^*(q_F,y)=q_j \} $
    \item $\Sigma'= \Sigma \times \Sigma $.
    \item $q'_0 = (q_0, q_F)$.
    \item $F' = \{ (q_h,q_h) \in Q \times Q \ | \ \exists u,v$, $uv \in R, |u|=|v|, \delta^*(q_0,u)= \delta_B^*(q_F,v)=q_h \} $
    \item Define $\delta'$ as: $\delta'( (q_i,q_j), (a,a) )= (p_i, p_j) $, with $\delta(q_i,a) = p_i$ and $\delta_B(q_j,a) = p_j$.
\end{itemize}

Transform the NFA $N'$ into NFA $\hat{N}$, by changing $\Sigma'$ back to $\Sigma$ by ignoring the second symbol in the  transactions of NFA $N'$.\\

It is easy to show that the NFA $\hat{N}$ has the language $L = \{u\ \mid \exists v\in\Sigma^*,\, uv\in R,\, |u| = |v|\}$.
Since for every string $u$ accepted by $\hat{N}$, if we travel back in NFA $N'$ the second symbol will form a string $v$, it is easy to see that $ uv \in R, |u| = |v| $. Then we have $L$ is a regular language.

\vspace {0.5cm}\noindent
{\bf Solution B5.}

\vspace {0.5cm}\noindent
(1) Proof:
\begin{itemize}
    \item $ D_{xy} L = \{xy \in \Sigma^* \ | \ xyw \in L\} $; $ D_x L = \{x \in \Sigma^* \ | \ xw \in L\} $, $ D_y ( D_x L) = \{y \in \Sigma^* \ | \ yw' \in D_x L \} $, then we have $ D_{xy} L =  D_y ( D_x L) $.
    \item $ D_{\epsilon} L = \{ \epsilon w \in L\} = L $.
    \item $ D_x (A \cup B) = \{x \in \Sigma^* \ | \ xw \in A \cup B \} = \{x \in \Sigma^* \ | \ xw \in A \} \cup \{x \in \Sigma^* \ | \ xw \in B \} = D_x A \cup D_x B $.
    \item $ D_a (AB) = \{a \in \Sigma \ | \ auv \in AB, au \in A, v \in B \} $, if $ \epsilon \in A $, $ D_a (\epsilon B) = \{ a \in \Sigma \ | \ av \in B \} $; then we have $ D_{a} (AB) = (D_a A) B \cup (A \cap \{\epsilon\}) D_a B $.
    \item It is trivial to show $\epsilon$ belong to both sides of equation, for any string except $\epsilon$, $ D_a(L^*) = \{a \in \Sigma \ | \ auv \in L^*, au \in L, v \in L^*\} = \{a \in \Sigma \ | \ auv \in L^*, au \in L, u \in D_a L, v \in L^*\} = (D_a L) L^* $
\end{itemize}

\vspace {0.5cm}\noindent
(2)(i) Proof:
Construct a parser tree for the regular expression $R$, for example the parser tree of $((a+b)c)^*$ is shown below:

\begin{figure}[h]
\begin{center}
  % Requires \usepackage{graphicx}
  \includegraphics[width=0.15\linewidth]{fig_3}
  \caption{The example parser tree}\label{fig_B3}
\end{center}
\end{figure}

Using the recursive algorithm $ boolean \ Test(node \ p)$ from the root node $p$ of the tree:

\begin{itemize}
    \item If node p is labeled $\epsilon$, return $True$;
    \item If node p is labeled $\Sigma$ or $\emptyset$, return $False$;
    \item If node p is labeled $*$, return $True$;
    \item If node p is labeled $\cdot$, return $Test(p.LeftChild) \ \wedge \ Test(p.RightChild) $;
    \item If node p is labeled $+$, return $Test(p.LeftChild) \ \vee \ Test(p.RightChild) $;
\end{itemize}

If the result is $True$ then $\epsilon \in \s{L}[R]$, else $\epsilon \notin \s{L}[R]$.\\

\vspace {0.5cm}\noindent
(2)(ii) Proof:
We first transfer a regular expression $R'$ into $R$ by performing the following operations:
\begin{itemize}
    \item For all the pattern $(s_1+ \cdots +s_n)$, where $s_i$ $(i=1,\cdots\,n)$ is substring of $R'$ that does not contain $+$ symbol, transform to the format $u(s'_1+ \cdots +s'_n)v$, where $u,v$ are respectively, longest common prefix and longest common suffix of $s_i$ $(i=1,\cdots\,n)$. It is easy to see that $u,v$ do not contain $+$ symbol.
    \item For the remaining pattern $(s'_1+ \cdots +s'_n)$, replace this pattern with any first symbol of $s_i$, for example both pattern $(a+bc)$, and $(a+b)$ are replaced by either $a$ or $b$.
\end{itemize}

Then we get regular expression $R$, and it is easy to show that $R$ and $R'$ has the same set of distinct derivatives.\\

Given a regular expression $R$, assume the number of occurrences of the symbols from $\Sigma \cup \{\epsilon, \emptyset, +, \cdot, *\}$ is $l$.

\begin{enumerate}
    \item
        \begin{itemize}
        \item When $l=1$, to be valid, $R=a, a \in \Sigma$, the set of all the distinct derivatives are $\{R, \epsilon, \emptyset\}$. As we can see, except $\epsilon$ and $\emptyset$, $\{R\}$ is set of all the suffix of $\s{L}[R]$.
        \item When $l=2$, to be valid, $R=a^*, a \in \Sigma$, the set of all the distinct derivatives are $\{R, \epsilon, \emptyset\}$. As we can see, except $\epsilon$ and $\emptyset$, $\{R\}$ is set of all the suffix of $\s{L}[R]$.
        \item When $l=3$, to be valid, $R=a \cdot b, a,b \in \Sigma$, the set of all the distinct derivatives are $\{ab, b, \epsilon, \emptyset\}$. As we can see, except $\epsilon$ and $\emptyset$, $\{ab, b\}$ is set of all the suffix of $\s{L}[a \cdot b]$.
        %\item When $l=3$, to be valid, $R=a + b, a,b \in \Sigma$, the set of all the distinct derivatives are $\{a, b, \epsilon, \emptyset\}$. As we can see, except $\epsilon$ and $\emptyset$, $\{R\}$ is set of all the suffix of $\s{L}[R]$.
    \end{itemize}

    \item Assume when the number of occurrences of the symbols of $R$ is $n$, $R$ has finitely many distinct derivatives.
    \item
        \begin{itemize}
            \item When $l=n+1$, to be valid, $R=Q^*$, where $Q$ is a regular expression with the number of occurrences of the symbols $n$, using induction hypothesis, the set of all the distinct derivatives of $Q$ is $\{ D(Q), \epsilon, \emptyset \}$, $D(Q)$ is all the distinct derivatives besides $\epsilon$ and $\emptyset$. For each distinct derivative, we denote it as $D(q)$, and $ D(q) \in D(Q)$. Then the set of all the distinct derivatives of $R$ is $\{ D(q)^* \ | \ D(q) \in D(Q)\}\cup\{ \epsilon, \emptyset \}$.
            %\item When $l=n+2$, to be valid, $R=Q+a$, where $a \in \Sigma$, and $Q$ is a regular expression with the number of occurrences of the symbols $n$, using induction hypothesis, the set of all the distinct derivatives of $Q$ is $\{ D(Q), \epsilon, \emptyset \}$, $D(Q)$ is all the distinct derivatives besides $\epsilon$ and $\emptyset$. Then the set of all the distinct derivatives of $R$ is $\{ D(Q), \epsilon, \emptyset \} \cup \{a\}$.
            \item When $l=n+2$, to be valid, $R=Q \cdot a$, where $a \in \Sigma$, and $Q$ is a regular expression with the number of occurrences of the symbols $n$, using induction hypothesis, the set of all the distinct derivatives of $Q$ is $\{ D(Q), \epsilon, \emptyset \}$, $D(Q)$ is all the distinct derivatives besides $\epsilon$ and $\emptyset$. For each distinct derivative, we denote it as $D(q)$, and $ D(q) \in D(Q)$. Then the set of all the distinct derivatives of $R$ is $\{ D(q) \cdot a \ | \ D(q) \in D(Q)\}\cup\{ \epsilon, \emptyset \}$.
        \end{itemize}
\end{enumerate}
As we can see, since the number of occurrences of the symbols of $R$ is finite, following the induction above, the number of all the distinct derivatives is also finite.

\vspace {0.5cm}\noindent
(3)(i) Proof by contradiction: 
Assume there exists $D_x R$ which does not belong to the finite set $D_n\ =\ \{D_x R\ |\ x\in \Sigma^*, 0\leq|x| < n\}.$, clealy $x \geq n$.

First we prove the following lemma:

\textbf{Lemma} : If for some $m,n \in \mathrm{Z}, 0\leq m < n$, $D_m R=
D_n R$, then $\forall x\geq n, \exists m\leq y< n\ \ni D_x R = D_y R$.

Proof by induction:
\begin{itemize}
  \item Let $x = n$, by condition $D_x R = D_n R = D_m R$, so let $y=m,\ D_x = D_y$
  \item Suppose for some $x\geq n,\ \exists m\leq y< n\ \ni D_x R = D_y R$. \\It follows $D_{x+1} R = D_{xa} R = D_a (D_x R) = D_a (D_y R) = D_{y+1} R$, notice that $ m\leq y< n \rightleftharpoons m\leq (y+1)\leq n$. If $m\leq (y+1)< n$, then we found $y_1 = y+1\in \left[m,n\right)\ \ni D_{x+1} = D_{y_1}$; If $y+1 = n$, notice $D_{x+1} = D_{y+1} = D_n = D_m$, we found $y_1 = m\in \left[m,n\right)\ \ni D_{x+1} = D_{y_1}$. Either way, we proof the induction step is true.
\end{itemize}

Now we add $D_x$ to $D_n$ and form a new set $D_{n+1}\ =\ \{\{D_x\},\ D_n \}$. It has $n+1$ derivatives but we know $R$ has only $n$ distinct derivatives. By principle of pigeon house, there $\exists D_p,D_q \in D_{n+1}\ \ni D_p = D_q,\ say\ p < q$. By assumption, $D_x \notin D_n$, which means $ D_p,D_q \in D_n \rightharpoonup m\leq p,q < n$. By the lemma we just prove, $D_p = D_q \rightharpoonup \forall x\geq q, \exists p\leq y< q\ \ni D_x R = D_y R$, and $m\leq p,q < n,\ x\geq n \rightharpoonup x > q$. So certainly for $x > q$, there should $\exists p\leq y< q\ \ni D_x R = D_y R$, notice that particular$D_y \in D_n$, this contradicts the fact that $D_x \notin D_n$. 

Assumption fails which means every derivative of $R$ belongs to the finite set $D_n$. 

\vspace {0.5cm}\noindent
(3)(ii) Proof: Assume the length of $R$ is $n$, then the length of the derivatives are less or equal to $n$. Assume the number of all possible symbols from $\Sigma \cup \{\epsilon,\emptyset,+,\cdot,*\}$ is $m$, for a derivative of length $i$, the number of possible combinations is less than $m^i$, for all length from $0$ to $n$, the upper bound will be $\Sigma_{i=1}^n m^i$.

\vspace {0.5cm}\noindent
(4) Proof: 
\begin{itemize}
\item
Suppose $D = (Q,\Sigma,\delta,q_0,F)$ is a DFA accepting $\s{L}[R]$
and $D$ has $n$ states. First we construct a new DFA $D' = (Q,\Sigma,\delta,q'_0 = \delta^*(q_0,x),F)$, notice that $w\in L[D'] \rightleftharpoons \delta^*(q'_0,w) \in F \rightleftharpoons \delta^*(q'_0,w) = \delta^*(\delta^*(q_0,x),w) = \delta^*(q_0,xw) \in F \rightleftharpoons xw \in L[D]$. So $w\in L[D'] \rightleftharpoons xw\in \s{L}[R]$. Therefore the new DFA $D' = (Q,\Sigma,\delta,q'_0 = \delta^*(q_0,x),F)$ is the DFA accepts $\s{L}[D_x R]$. In another word, for every $D_x$, there exists a particular DFA $D' = (Q,\Sigma,\delta,q'_0 = \delta^*(q_0,x),F)$ accepting it.
Notice that there are only $n$ states in $D$, which implies $\delta^*(q_0,x)$ has at most $n$ possibilities. So there are at most $n$ distinct $D'$, which means $R$ has at most $n$ distinct derivatives.
\item If $\nu(R)$ is the number of occurrences in $R$ of the symbols from $\Sigma \cup \{\epsilon, \emptyset, +, \cdot, *\}$, to consider how many distinct derivatives $R$ has, recall the recursive algorithm we used to convert regular expression to equivalent NFA. 

For every symbol $a$ in $R$, if $a\in\Sigma$, we need a two-state NFA to representing the expression $a$. There are at most $\nu(R)$ symbols in $R$ come from $\Sigma$, that's $2\nu(R)$ states in total. Now consider symbols from $\{\epsilon, \emptyset, +, \cdot, *\}$. $\epsilon$ and $\emptyset$ need no more than two states for each, which means that two symbols do not add new states to $2\nu(R)$. Recall that in the recursive algorithm, operations for  $\{+, \cdot, *\}$ do not add any new state into the NFA (if we choose one of the start state as new start state, the same to final state). So in conclusion, a NFA accepting $R$ has no more than $2\nu(R)$ states. We know a NFA with $n$ states can be converted to a equivalent DFA which has no more than $2^n$ states. So the DFA accepting $R$ has at most $2^{2\nu(R)}$ states. From the first conclusion, we know $R$ has at most $2^{2\nu(R)}$ distinct derivatives. It is trivial that $\nu(R) \leq |R|$, so in another word, $R$ has at most $2^{2\nu(R)}<4^{|R|}$ distinct derivatives.

  
\end{itemize}
\vspace {0.5cm}\noindent
(5) Proof: \\

We firstly prove that, for any regular language $L$ over $\Sigma^*$,
if $D_uL$ and $D_vL$ are two different derivatives, then
$D_uL=\{x\in\Sigma^*|\delta^*(q_u, x)\in F, q_u\in Q\}$,
$D_vL=\{x\in\Sigma^*|\delta^*(q_v, x)\in F, q_v\in Q\}$, and
$q_u\neq q_v$. The reason is, by definition,
$D_xL=\{y\in\Sigma^*|xy\in L, x\in\Sigma^*\}$, so we have $\forall
y\in D_xL$, $\delta^*(\delta^*(q_0,x), y)\in F$. Here if
$\delta^*(q_0,u)=\delta^*(q_0,v)$, then $D_uL=D_vL$. So if $D_uL\neq
D_vL$, then we have two different corresponding $q_u, q_v\in Q$.\\

Suppose $D$ is a minimal DFA for $L$ which has $n$ states, and $L$
has $k$ distinct derivatives.
\begin{itemize}
\item If $k>n$, by the proposition proved above, $D$ must have $k$
different states. This contradicts with that $D$ has $n$ states. So
$k\leq n$.

\item If $k<n$, $D$ must have at least two different states
$q_u,q_v$ so that $\{y\in\Sigma^*|\delta^*(q_u,y)\in
F\}=\{y\in\Sigma^*|\delta^*(q_v,y)\in F\}$. This means we can get a
smaller DFA for $L$ by combining $q_u$ and $q_v$, which contradicts
that $D$ is a minimal DFA. So $k\geq n$. In all we have that $k=n$.
\end{itemize}

\begin{figure}[h]
\begin{center}
  % Requires \usepackage{graphicx}
  \includegraphics[width=0.5\linewidth]{fig_4}
  \caption{The DFA for question (6)}
  \label{fig_b5}
  
\end{center}
\end{figure}

(6) Proof:\\
It is easy to show that $\nu(R) = 3n + 5$, by simply counting the symbols.\\

We could have $2^{n+1}$ strings from $\underbrace{(a + b) \cdots (a + b)}_{n+1}$, namely from $\underbrace{a \cdots a}_{n+1}$ to $\underbrace{b \cdots b}_{n+1}$. We claim that the $2^{n+1}$ derivatives, $D_{a \cdots a}$ to $D_{b \cdots b}$, are distinct.\\

To any two derivatives $D_{1}R$ and $D_{2}R$ from the $2^{n+1}$ derivatives above, then we can write them into $D_{sau}$ and $D_{sbv}$, where $s=a^*$, $|u|=|v|=i$, then $\underbrace{(a + b) \cdots (a + b)}_{n+1-i} \in D_{sau}R$, and $\underbrace{(a + b) \cdots (a + b)}_{n+1-i} \notin D_{sau}R$. Then, they are derivatives.\\

Figure \ref{fig_b5} shows the DFAs met the requirement.\\


According to (4) we just proved, since $R$ has $2^{n+1}$ distinct derivatives, the DFA accepted $R$ has at least $2^{n+1}$ states. It is easy to construct a NFA to accept $R$ with $n+1$ states, we can convert the NFA to DFA, and that DFA will have at most $2^{n+1}$ states. Then we conclude that any minimal DFA for the language denoted by $R$ above has $2^{n+1}$ states.

\end{document}
